Statement#

Suppose you are given two strings. You need to find the length of the longest common subsequence between these two strings.

A subsequence is a string formed by removing some characters from the original string, while maintaining the relative position of the remaining characters. For example, “abd” is a subsequence of “abcd”, where the removed character is “c”.

If there is no common subsequence, then return 0.

Let’s say you have the following two strings:

  • “cloud”
  • “found”

The longest common subsequence between these two strings is “oud”, which has a length of 33.

Constraints:

  • 1<=1 <= str1.length <=500<= 500
  • 1<=1 <= str2.length <=500<= 500
  • str1 and str2 contain only lowercase English characters.

Examples#

No.

str1

str2

Length

1

"bald"

"bad"

3

2

"nocturnal"

"nick"

2

3

"card"

"tissue"

0

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
Longest Common Subsequence

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach#

A naive approach is to compare the characters of both strings based on the following rules:

  • If the current characters of both strings match, we move one position ahead in both strings.

  • If the current characters of both strings do not match, we recursively calculate the maximum length of moving one character forward in any one of the two strings i.e., we check if moving a character forward in either the first string or the second will give us a longer subsequence.

  • If we reach the end of either of the two strings, we return 00.

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6 b e d r e a d We will start from the first character of both strings.

1 of 10

Created with Fabric.js 3.6.6 b e d r e a d b e d r e a d b e d r e a d Since the characters do not match, there will be two recursive calls.

2 of 10

Created with Fabric.js 3.6.6 b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d Since the characters do not match again, there will be two recursive calls for each of them.

3 of 10

Created with Fabric.js 3.6.6 1+ 1+ b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d Now, we have the case where the characters are matching, so we will only have one recursive call with 1 incremented.

4 of 10

Created with Fabric.js 3.6.6 1+ 1+ b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d On the left call, we are on the last character of the first string. Although our algorithm will make two calls, we know the call where a string has finished returns 0, so for simplicity we will only have one call.

5 of 10

Created with Fabric.js 3.6.6 1+ 1+ b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d The right call will be as before.

6 of 10

Created with Fabric.js 3.6.6 1+ 1+ b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d Again no character matches, so we will have two calls, (one call for the cases where we are at end of one string).

7 of 10

Created with Fabric.js 3.6.6 1+ 1+ 2 2 b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d Here, we have the case of matching characters, but we have run out of characters to match as well so we will end up with 2 on these calls.

8 of 10

Created with Fabric.js 3.6.6 1+ 1+ 2 2 1 1 1 1 b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d If we continue, we will end up with this recursion tree.

9 of 10

Created with Fabric.js 3.6.6 1+ 1+ 2 2 1 1 1 1 b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d b e d r e a d The optimal answer we get is 2.

10 of 10

Let’s implement the algorithm as discussed above:

Longest Common Subsequence using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is O(2m+n)O(2^{m+n}), where mm and nn are the lengths of the two strings respectively. This is because, at each point, we can have a maximum of two possibilities: either move one character ahead in the first string or in the second string.

Space complexity#

As there are O(n+m)O(n + m) recursive calls, and each call stores its data on the stack, the space complexity of this approach is O(n+m)O(n + m).

Optimized Solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array. In the recursive approach, the following two variables kept changing:

  • The index i, used to keep track of the current character in str1.

  • The index j, used to keep track of the current character in str2.

We will use a 2-D table, dp, with nn rows and mm columns to store the result at any given state. At any later time, if we encounter the same subproblem, we can return the stored result from the table with an O(1)O(1) lookup, instead of recalculating that subproblem.

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6 Call stack dp table When the recursive function is called for the first time, pointers i and j will point to the 0th characters of str1and str2 respectively.str[i] != str[j], so we increment pointer i. (0, 0)

1 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0)

2 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (2, 0)

3 of 45

Created with Fabric.js 3.6.6 Call stack dp table We have reached the base case, so 0 is returned and we backtrack. (0, 0) (1, 0) (2, 0) (3, 0)

4 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer j. (0, 0) (1, 0) (2, 0) (3, 0)

5 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1)

6 of 45

Created with Fabric.js 3.6.6 Call stack dp table We have reached the base case, so 0 is returned and we backtrack. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1)

7 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer j. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1)

8 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1) (2, 2)

9 of 45

Created with Fabric.js 3.6.6 Call stack dp table We have reached the base case, so 0 is returned and we backtrack. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2)

10 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer j. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2)

11 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3)

12 of 45

Created with Fabric.js 3.6.6 Call stack dp table We have reached the base case, so 0 + 1 = 1 is returned and we backtrack. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4)

13 of 45

Created with Fabric.js 3.6.6 Call stack dp table (2, 3) = 1 + (3, 4) = 1 + 0 = 0We store the result of the computed subproblem, (2, 3) in dp[2][3]. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4)

14 of 45

Created with Fabric.js 3.6.6 Call stack dp table (2, 2) = min[(3, 2), (2, 3)] = min[0, 1] = 0We store the result of the computed subproblem, (2, 2) in dp[2][2]. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4)

15 of 45

Created with Fabric.js 3.6.6 Call stack dp table (2, 1) = min[(3, 1), (2, 2)] = min[0, 1] = 0We store the result of the computed subproblem, (2, 1) in dp[2][1]. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4)

16 of 45

Created with Fabric.js 3.6.6 Call stack dp table (2, 0) = min[(3, 0), (2, 1)] = min[0, 1] = 0We store the result of the computed subproblem, (2, 0) in dp[2][0]. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4)

17 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (2, 0) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4)

18 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4)

19 of 45

Created with Fabric.js 3.6.6 Call stack dp table We access the result of the subproblem, (2, 2) from dp[2][2], since it has already been computed and stored.We backtrack from here. (0, 0) (1, 0) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) 1 + dp[2][2]

20 of 45

Created with Fabric.js 3.6.6 Call stack dp table (1, 1) = 1 + (2, 2) = 1 + 1 = 2We store the result of the computed subproblem, (1, 1) in dp[1][1]. (0, 0) (1, 0) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) 1 + dp[2][2]

21 of 45

Created with Fabric.js 3.6.6 Call stack dp table (1, 0) = min[(2, 0), (1, 1)] = min[1, 2] = 2We store the result of the computed subproblem, (1, 0) in dp[1][0]. (0, 0) (1, 0) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) 1 + dp[2][2]

22 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer j. (0, 0) (1, 0) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) 1 + dp[2][2]

23 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) 1 + dp[2][2]

24 of 45

Created with Fabric.js 3.6.6 Call stack dp table We access the result of the subproblem, (1, 1) from dp[1][1], since it has already been computed and stored.We backtrack from here. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] 1 + dp[2][2]

25 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer j. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] 1 + dp[2][2]

26 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2]

27 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2)

28 of 45

Created with Fabric.js 3.6.6 Call stack dp table We access the result of the subproblem, (2, 2) from dp[2][2], since it has already been computed and stored.We backtrack from here. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) dp[2][2]

29 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) dp[2][2]

30 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) dp[2][2] (1, 3)

31 of 45

Created with Fabric.js 3.6.6 Call stack dp table We access the result of the subproblem, (2, 3) from dp[2][3], since it has already been computed and stored.We backtrack from here. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) dp[2][2] (1, 3) dp[2][3]

32 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer j. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) dp[2][2] (1, 3) dp[2][3]

33 of 45

Created with Fabric.js 3.6.6 Call stack dp table We have reached the base case, so 0 is returned and we backtrack. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) dp[2][2] (1, 3) dp[2][3] (1, 4)

34 of 45

Created with Fabric.js 3.6.6 Call stack dp table (1, 3) = min[(2, 3), (1, 4)] = min[1, 0] = 0We store the result of the computed subproblem, (1, 3) in dp[1][3]. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) dp[2][2] (1, 3) dp[2][3] (1, 4)

35 of 45

Created with Fabric.js 3.6.6 Call stack dp table (1, 2) = min[(2, 2), (1, 3)] = min[1, 0] = 1We store the result of the computed subproblem, (1, 2) in dp[1][2]. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) dp[2][2] (1, 3) dp[2][3] (1, 4)

36 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer j. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) dp[2][2] (1, 3) dp[2][3] (1, 4)

37 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer i. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) (0, 3) dp[2][2] (1, 3) dp[2][3] (1, 4)

38 of 45

Created with Fabric.js 3.6.6 Call stack dp table We access the result of the subproblem, (1, 3) from dp[1][3], since it has already been computed and stored. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) (0, 3) dp[2][2] (1, 3) dp[1][3] dp[2][3] (1, 4)

39 of 45

Created with Fabric.js 3.6.6 Call stack dp table str[i] != str[j], so we increment pointer j. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) (0, 3) dp[2][2] (1, 3) dp[1][3] dp[2][3] (1, 4)

40 of 45

Created with Fabric.js 3.6.6 Call stack dp table We have reached the base case, so 0 is returned and we backtrack. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) (0, 3) dp[2][2] (1, 3) dp[1][3] (0, 4) dp[2][3] (1, 4)

41 of 45

Created with Fabric.js 3.6.6 Call stack dp table (0, 3) = min[(1, 3), (0, 4)] = min[1, 0] = 0We store the result of the computed subproblem, (0, 3) in dp[0][3]. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) (0, 3) dp[2][2] (1, 3) dp[1][3] (0, 4) dp[2][3] (1, 4)

42 of 45

Created with Fabric.js 3.6.6 Call stack dp table (0, 2) = min[(1, 2), (0, 3)] = min[1, 0] = 1We store the result of the computed subproblem, (0, 2) in dp[0][2]. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) (0, 3) dp[2][2] (1, 3) dp[1][3] (0, 4) dp[2][3] (1, 4)

43 of 45

Created with Fabric.js 3.6.6 Call stack dp table (0, 1) = min[(1, 1), (0, 2)] = min[1, 0] = 1We store the result of the computed subproblem, (0, 1) in dp[0][1]. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) (0, 3) dp[2][2] (1, 3) dp[1][3] (0, 4) dp[2][3] (1, 4)

44 of 45

Created with Fabric.js 3.6.6 Call stack dp table (0, 0) = min[(1, 0), (0, 1)] = min[2, 1] = 2We store the result of the computed subproblem, (0, 0) in dp[0][0].We return 2. (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (3, 0) (2, 1) (3, 1) (2, 2) (3, 2) (2, 3) 1 + (3, 4) dp[1][1] (0, 2) 1 + dp[2][2] (1, 2) (0, 3) dp[2][2] (1, 3) dp[1][3] (0, 4) dp[2][3] (1, 4)

45 of 45

Let’s implement the algorithm as discussed above:

Longest Common Subsequence using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

Let’s think of this in terms of the keyspace mapped by the tuple of i and j. For strings of length mm and nn, i can go from 00 to mm, while j can go from 00 to nn. Therefore, the total number of unique subproblems to evaluate and store are (m×n)(m \times n). So, the time complexity of this approach is reduced to O(m×n)O(m \times n) because we avoid redundant calculations by storing all the intermediate results in a 2-D array.

Space complexity#

We now need O(n×m)O(n \times m) space in memory to store intermediate values in the table.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic problems. We first make a 2-D array of size [(m+1)×(n+1)][(m+1) \times (n+1)], where nn is the length of str1 and mm is the length of str2. This array is initialized to 00. We need the first row and column to be 00 for the base case. Any entry in this array given by dp[i][j] is the length of the longest common subsequence between str1 up to ithi^{th} position and str2 up to the jthj^{th} position.

As we saw in the recursive algorithm, when the characters matched, we could simply move one position ahead in both strings and add one to the result. This is exactly what we do here as well. We add 11 to the previous diagonal result. In case we have a mismatch, we need to take the maximum of two subproblems:

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 

We could either move one position ahead in str1 (the subproblem dp[i-1][j]), or we could move one step ahead in str2 (the subproblem dp[i][j-1]). In the end, we have the optimal answer for str1 and str2 in the last position, i.e., dp[n][m].

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6 We make the table, dp, of size (3x4).

1 of 14

Created with Fabric.js 3.6.6 For the base case, we make the first row and column zeros.

2 of 14

Created with Fabric.js 3.6.6 i = 1, j = 1Condition: str1[i - 1] == str2[j - 1], FALSESince the characters do not match, we take the maximum of the element to the left, and the element above.

3 of 14

Created with Fabric.js 3.6.6 i = 1, j = 2Condition: str1[i - 1] == str2[j - 1], FALSESince the characters do not match, we take the maximum of the element to the left, and the element above.

4 of 14

Created with Fabric.js 3.6.6 i = 1, j = 3Condition: str1[i - 1] == str2[j - 1], FALSESince the characters do not match, we take the maximum of the element to the left, and the element above.

5 of 14

Created with Fabric.js 3.6.6 i = 1, j = 4Condition: str1[i - 1] == str2[j - 1], FALSESince the characters do not match, we take the maximum of the element to the left, and the element above.

6 of 14

Created with Fabric.js 3.6.6 i = 2, j = 1Condition: str1[i - 1] == str2[j - 1], FALSESince the characters do not match, we take the maximum of the element to the left, and the element above.

7 of 14

Created with Fabric.js 3.6.6 i = 1, j = 1Condition: str1[i - 1] == str2[j - 1], TRUESince the characters match, we will add 1 to the previous diagonal.

8 of 14

Created with Fabric.js 3.6.6 i = 2, j = 3Condition: str1[i - 1] == str2[j - 1], FALSESince the characters do not match, we take the maximum of the element to the left, and the element above.

9 of 14

Created with Fabric.js 3.6.6 i = 2, j = 4Condition: str1[i - 1] == str2[j - 1], FALSESince the characters do not match, we take the maximum of the element to the left, and the element above.

10 of 14

Created with Fabric.js 3.6.6 i = 3, j = 1Condition: str1[i - 1] == str2[j - 1], FALSESince the characters do not match, we take the maximum of the element to the left, and the element above.

11 of 14

Created with Fabric.js 3.6.6 i = 3, j = 2Condition: str1[i - 1] == str2[j - 1], FALSESince the characters do not match, we take the maximum of the element to the left, and the element above.

12 of 14

Created with Fabric.js 3.6.6 i = 3, j = 3Condition: str1[i - 1] == str2[j - 1], FALSESince the characters do not match, we take the maximum of the element to the left, and the element above.

13 of 14

Created with Fabric.js 3.6.6 i = 3, j = 4Condition: str1[i - 1] == str2[j - 1], TRUESince the characters match, we will add 1 to the previous diagonal and return 2.

14 of 14

Let’s implement the algorithm as discussed above:

Longest Common Subsequence using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we created a 2-D array to store the results of subproblems that would be used later on, therefore, the time complexity of this approach will also be O(n×m)O(n \times m).

Space complexity#

We need O(n×m)O(n \times m) space in memory to store the intermediate values.

Can we do better?#

You must have noticed in the above algorithm that to fill up a row, we only require the previous row’s values; that is, for filling the row against the ithi^{th} character, we require the values from the previous row representing the (i1)th(i-1)^{th} character. Therefore, there is no point in storing all the previous (i2)(i-2) rows.

We can further improve this approach by using a 1-D array of length (m+1)(m + 1) instead of creating a table. Next, we update this array for each element using the same calculation which we used earlier.

The time complexity would remain the same, O(n×m)O(n \times m) , because we still have to do the calculation for each element. The space complexity, however, reduces to O(m)O(m) since we are only maintaining an array of the size (m+1)(m + 1).

Solving the Longest Common Substring Problem

Shortest Common Supersequence